package array;

public class leetcode189 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7};
        int k = 3;
        rotate2(nums, k);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    //三次翻转法
    public static void rotate(int[] nums, int k){
        if(nums.length <= 1) return;

        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if( i+k <= nums.length - 1){
                result[i+k] = nums[i];
            }
            else {
                result[(i+k)%nums.length] = nums[i];
            }
        }

        for (int i = 0; i < nums.length; i++){
            nums[i] = result[i];
        }
    }

    public static void rotate2(int[] nums, int k){
        int n = nums.length;
        k %= n;  // 处理k大于n的情况
        if(n < 2 || k == 0) return;

        reverse(nums, 0, n-1);  // 整体反转
        reverse(nums, 0, k-1);   // 前k个反转
        reverse(nums, k, n-1);   // 剩余部分反转
    }

    private static void reverse(int[] nums, int start, int end) {
        while(start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}
